package com.skh.array;

import java.util.Arrays;

/**
 * @Author: skh
 * @Date: 2019/6/24 13:47
 * @Description: 1051 高度检查器
 */
public class HeightChecker {

    /*
    学校在拍年度纪念照时，一般要求学生按照 非递减 的高度顺序排列。

请你返回至少有多少个学生没有站在正确位置数量。该人数指的是：能让所有学生以 非递减 高度排列的必要移动人数。

    示例：

    输入：[1,1,4,2,1,3]
    输出：3
    解释：
    高度为 4、3 和最后一个 1 的学生，没有站在正确的位置。

     */

    /*
    思路:题目仅要求返回移动人数，即与非递减排列的 Hamming Distance

    因此将传入数组与排序后的数组对比即可
     */
    public int heightChecker(int[] heights) {
        int[] copy = Arrays.copyOf(heights, heights.length);
        Arrays.sort(heights);

        int diff =0;
        for (int i = 0; i < heights.length; i++) {
            if (copy[i] != heights[i]) {
                diff++;
            }
        }

        return diff;
    }
}
